[[abstract]]Given a permutation graph G with its corresponding permutation pi, we present an algorithm for finding a minimum cardinality dominating set for G. Our algorithm runs in O(n) time in amortized sense where n is the number of vertices in G. Hence, it is optimal. The best previous result is an O(n log log n) algorithm.
展开▼
